//
// Created by ASUS on 2024/2/28.
//

//无修改节点只查询
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

class Node{
public:
	int l,r;
	int mx1=INT_MIN,mx2=INT_MIN;
};

class segmentTree{
public:
	int n;
	vector<Node> t;
	explicit segmentTree(vector<int>&a){
		n=a.size();
		t=vector<Node>(4*n);
		build(1,1,n,a);
	}
	~segmentTree()= default;

	void pushup(int i){
		t[i].mx1=max(t[2*i].mx1,t[2*i+1].mx1);
		t[i].mx2=max(max(t[2*i].mx2,t[2*i+1].mx2),min(t[2*i].mx1,t[2*i+1].mx1));
	}

	void build(int i,int l,int r,vector<int>&a){
		t[i].l=l;
		t[i].r=r;
		if(l==r){
			t[i].mx1=a[l];
			t[i].mx2=INT_MIN;
			return;
		}
		int mid=l+(r-l)/2;
		build(i*2,l,mid,a);
		build(i*2+1,mid+1,r,a);
		pushup(i);
	}

	//查询最大值
	ll query1(int i,int l,int r){
		if(t[i].l>r||t[i].r<l) return INT_MIN;
		if(t[i].l>=l&&t[i].r<=r){
			return t[i].mx1;
		}
		return max(query1(2*i,l,r),query1(2*i+1,l,r));
	}

	//查询最大值
	ll query1(int l,int r){
		return query1(1,l,r);
	}

	//查询次大值
	ll query2(int i,int l,int r){
		if(t[i].l>r||t[i].r<l) return INT_MIN;
		if(t[i].l>=l&&t[i].r<=r){
			return t[i].mx2;
		}
		return max(max(query2(2*i,l,r),query2(2*i+1,l,r)),min(query1(2*i,l,r),query1(2*i+1,l,r)));
	}

	//查询次大值
	ll query2(int l,int r){
		return query2(1,l,r);
	}
};

int main(){
	vector<int> a{0,1,3,6,-1,3,8};
	segmentTree seg(a);
	cout<<seg.query1(5,5)<<" "<<seg.query2(5,5)<<endl;
	return 0;
}